BFS—Complexity & Memory - Educational Content

Using an adjacency list, BFS runs in linear time relative to the size of the graph, making it highly efficient.

Time Complexity: The total runtime is $O(V+E)$. This is because each vertex is enqueued and dequeued exactly once ($O(V)$), and every edge is explored at most twice in an undirected graph ($O(E)$).
Space Complexity: The extra memory required is $O(V)$. This is needed for the `visited` set, `parent` and `level` maps, and the queue itself.
The queue size is the main variable in space usage. In the worst-case scenario (a very wide, shallow graph), the queue might hold nearly all vertices at once, leading to $O(V)$ space.
The efficiency of BFS heavily relies on using an adjacency list, which allows finding all neighbors of a vertex in time proportional to its degree.

Time = $O(V+E)$
Space = $O(V)$